package com.JAVA程序员面试宝典;

/**
 * LinkedList有序
 * @author qiuxiaochen
 *
 */
public class 实现排序LinkedList {
	private class Data {
		private Integer object;
		private Data next = null;

		public Data(Integer object) {
			this.object = object;
		}
	}

	private Data first = null;

	public void insert(Integer obj) {
		Data data = new Data(obj);
		if (first == null)
			first = data;
		else {
			if (obj < first.object) {
				data.next = first.next;
				first = data;
			} else {
				Data pre = first;
				Data cur = first.next;
				while (cur != null) {
					if (cur.object < obj) {
						pre = cur;
						cur = cur.next;
					} else {
						break;
					}
				}
				pre.next = data;
				data.next = cur;
			}
		}
	}

	public Object deleteFirst() {
		if (first == null) {
			System.out.println("The stack is empty!!");
			return null;
		} else {
			first = first.next;
			return first.object;
		}
	}

	public Object find(Object obj) {
		if (first == null) {
			System.out.println("The stack is empty!!");
			return null;
		} else {
			Data cur = first;
			while (cur != null) {
				if (cur.object.equals(obj)) {
					return cur.object;
				}
				cur = cur.next;
			}
			return null;
		}
	}

	public void delete(Integer obj) {
		if (first == null) {
			System.out.println("The stack is empty!!");
			return;
		}
		while (first.object.equals(obj)) {
			first = first.next;
		}
		Data pre = first;
		Data cur = first.next;
		while (cur != null) {
			if (cur.object.equals(obj)) {
				pre.next = cur.next;
				cur = cur.next;
				continue;
			}
			pre = cur;
			cur = cur.next;
		}
	}

	public void display() {
		if (first == null) {
			System.out.println("The stack is empty!!");
		} else {
			Data cur = first;
			while (cur != null) {
				if (cur.next == null)
					System.out.print(cur.object);
				else
					System.out.print(cur.object + "---->");
				cur = cur.next;
			}
		}
		System.out.println();
	}

	public static void main(String[] args) {
		实现排序LinkedList linkedList = new 实现排序LinkedList();
		linkedList.insert(1);
		linkedList.insert(88);
		linkedList.insert(22);
		linkedList.insert(24);
		linkedList.insert(35);
		linkedList.insert(13);
		linkedList.insert(993);
		linkedList.insert(77);
		linkedList.display();
		linkedList.insert(0);
		linkedList.display();
		linkedList.insert(15);
		linkedList.display();
		linkedList.insert(1000);
		linkedList.display();
	}

}
